// 快排的思想：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。
// 我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。
// 经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。
// 根据分治、递归的处理思想，我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据，直到区间缩小为 1，就说明所有的数据都有序了。

// 递推公式：
// quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1… r)

// 终止条件：
// p >= r

//  11 8 3 9
//  8 3 9 11
//  3 8 9 11

const arr = [11, 8, 3, 9, 7, 1, 2, 5];
function quick_sort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  let pivot = arr.pop();
  let left = [],
    right = [];

  for (let i in arr) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return [...quick_sort(left), pivot, ...quick_sort(right)];
}

// 原地调整
// 6 11 3 9 8
// 6 11 3 9 8
// 6 11 3 9 8
// 6 3 11 9 8
// 6 3 11 9 8
// 6 3 8 9 11

const arr1 = [6, 11, 3, 9, 8];
function partition(arr, left, right) {
  const pivotVal = arr[right];
  let startIndex = left;
  for (let i = left; i < right; i++) {
    if (arr[i] < pivotVal) {
      swap(arr, i, startIndex);
      startIndex++;
    }
  }
  swap(arr, startIndex, right);
  return startIndex;
}

function quick_sort1(arr, i, j) {
  if (i < j) {
    const index = partition(arr, i, j);
    quick_sort1(arr, i, index - 1 < i ? i : index - 1);
    quick_sort1(arr, index + 1 > j ? j : index + 1, j);
  }
}

function swap(arr, i, j) {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

quick_sort1(arr1, 0, arr1.length - 1);
console.log("arr11-->", arr1);
